/**
 * 解法一：两个两个进行合并
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
let mergeKLists1 = function (lists) {
    if (lists.length === 0) return null;
    let res = null;
    for (let i = 0; i < lists.length; i++) {
        const nodeItem = lists[i];
        if (nodeItem === null) continue;
        res = mergeTwoListNode(res, nodeItem);
    }
    return res;
};

function mergeTwoListNode(res, nodeItem) {
    if (res === null) return nodeItem;

    let head = new ListNode(0),
        temp = head;
    while (res && nodeItem) {
        if (res.val > nodeItem.val) {
            temp.next = nodeItem;
            nodeItem = nodeItem.next;
        } else {
            temp.next = res;
            res = res.next;
        }
        temp = temp.next;
    }

    temp.next = res === null ? nodeItem : res;

    return head.next;
}

/**
 * 解法2：分治策略，递归排序
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
let mergeKLists2 = function (lists) {
    if (lists.length === 0) return null;
    return merge(lists, 0, lists.length - 1);
};

function merge(lists, l, r) {
    if (l === r) {
        return lists[l];
    }

    if (l > r) {
        return null;
    }

    let mid = (l + r) >> 1;
    return mergeTwoListNode(merge(lists, l, mid), merge(lists, mid + 1, r));
}

function mergeTwoListNode(res, nodeItem) {
    if (res === null || nodeItem === null) {
        return res === null ? nodeItem : res;
    }

    let head = new ListNode(0),
        tail = head,
        lListNode = res,
        rListNode = nodeItem;
    while (lListNode && rListNode) {
        if (lListNode.val > rListNode.val) {
            tail.next = rListNode;
            rListNode = rListNode.next;
        } else {
            tail.next = lListNode;
            lListNode = lListNode.next;
        }
        tail = tail.next;
    }

    tail.next = lListNode === null ? rListNode : lListNode;

    return head.next;
}

function ListNode(val, next) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
}

let l1 = new ListNode(1);
l1.next = new ListNode(4);
l1.next.next = new ListNode(5);

let l2 = new ListNode(1);
l2.next = new ListNode(3);
l2.next.next = new ListNode(4);
let l3 = new ListNode(2);
l3.next = new ListNode(6);
// console.log(mergeKLists([l1, l2, l3]));
